package leetcode_core.leetcode_1;

public class LowestCommonAncestor {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1.假如说就是一根空树,那么都不用找到了
        if(null == root){
            return null;
        }
        //2.如果root本身就是p或者q,比如root就是p节点,如果q存在于以root为根的树中,显然root就是最近公共祖先
        //就算q不存在以root为根的树中,按照情况3,我们也要返回那个存在的节点给它用
        if(root == q || root == p){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //1.这时候从底部开始向上回溯,一直回溯到这里,发现这时候刚好p和q异侧不用讲,这时候root肯定就是最近公共祖先
        if(left!=null && right!=null){
            return root;
        }
        //2.假如说我遍历到的这个节点,两个都是空的
        if(left == null && right == null){
            return null;
        }
        //3.情况3
        return left == null ?right : left;
    }
}
